import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/16 10:56
 * @description 两次二分查找
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public int waysToSplit(int[] nums) {
        int n = nums.length;
        int[] s = new int[n+1];
        int mod = (int)1e9+7;
        for(int i = 1; i <= n; i++){
            s[i] = s[i-1] + nums[i-1];
        }
        int res = 0;
        //[1, i], [i+1, x], [x+1, n]
        for(int i = 1; i <= n - 2; i++){
            if(s[i] * 3 > s[n]) {
                break;
            }
            int l = i + 1, r = n - 1;
            while(l < r){
                int mid = l + r >> 1;
                if(s[mid] - s[i] >= s[i]) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            int t = l;
            l = i + 1; r = n - 1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(s[n] - s[mid] >= s[mid] - s[i]) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            if(r >= t) {
                res = (res + r - t + 1) % mod;
            }
        }
        return res % mod;
    }
}
